import java.util.Arrays;

public class MemerialSearch {
    //给出记忆化递归的应用示例，常见的dfs会堆每次搜索过的循环进行记录
    //给出具体的例子：
    //给定一个数组{1，5，9，8，5，3} 获取相隔的最大和。例如： 5+8+3=16 那就是最大和为16
    //虽然还有简单的方式解决这个问题但是这里主要举例来说一下记忆化搜索。

    public static int rob(int[] nums){
        int[] memo=new int[nums.length]; //记忆化数组
        Arrays.fill(memo,-1);
        return tryBob(nums,0,memo);
    }
    public static int tryBob(int []nums,int index,int[] memo){
        if(index>=nums.length){
            return 0;
        }
        //记忆化搜索
        if(memo[index]!=-1){
            return memo[index];
        }
        int res=0;
        for (int i = index; i < nums.length ; i++) {
            res=Math.max(res,nums[i]+tryBob(nums,i+2,memo));
        }
        memo[index]=res;
        return res;
    }
    public static void main(String[] args){
        int []a={1,5,9,8,5,3};
        System.out.println("rob = " + rob(a));
    }
}
